#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define MAXNUM 100
typedef string VerTex;

// 邻接矩阵
typedef struct {
	int arcnum, vexnum;
	VerTex vex[MAXNUM];
	int arcs[MAXNUM][MAXNUM];
}Graph;

// 辅助数组
typedef struct {
	// 边的始点和终点
	VerTex head;
	VerTex tail;
	int lowcoat;
}Edge;

Edge edge[MAXNUM];

int Vexset[MAXNUM];

int LocateVex(const Graph& G, VerTex v) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vex[i] == v)
			return i;
	}
	return -1;
}

// 构建无向图
void CreateGraph(Graph& G) {
	cin >> G.vexnum >> G.arcnum;
	// 依次输入顶点信息
	for (int i = 0; i < G.vexnum; i++)
		cin >> G.vex[i];
	// 初始化邻接矩阵
	for (int i = 0; i < G.arcnum; i++)
		for (int j = 0; j < G.arcnum; j++)
			G.arcs[i][j] = INT32_MAX;
	for (int k = 0; k < G.arcnum; k++) {
		VerTex v1, v2;
		int w, i, j;
		cin >> v1 >> v2 >> w;
		// 查找位置
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);
		G.arcs[i][j] = G.arcs[j][i] = w;
		edge[k].head = v1;
		edge[k].tail = v2;
		edge[k].lowcoat = w;
	}
}

// 用于排序
bool compare(Edge a, Edge b) {
	return a.lowcoat < b.lowcoat;
}

void Kruskal(Graph& G) {
	// 先使用排序算法将辅助数组元素权值从小到大排序
	sort(edge, edge + G.arcnum, compare);
	int sum = 0;
	// 联通数组表示各顶点自成一个连通分量
	for (int i = 0; i < G.vexnum; i++)
		Vexset[i] = i;
	for (int i = 0; i < G.arcnum; i++) {
		int v1, v2;
		v1 = LocateVex(G, edge[i].head);
		v2 = LocateVex(G, edge[i].tail);
		int vs1, vs2;
		vs1 = Vexset[v1];
		vs2 = Vexset[v2];
		if (vs1 != vs2) {
			cout << edge[i].head << " " << edge[i].tail << " " << edge[i].lowcoat << endl;
			// 合并vs1和vs2两个分量，将两个集合统一编号
			for (int j = 0; j < G.vexnum; j++)
				if (Vexset[j] == vs2)
					Vexset[j] = vs1;
		}
	}
}

int main() {
	Graph G;
	CreateGraph(G);
	cout << "The minimum spanning tree obtained by Kruskal algorithm is as follows" << endl;
	Kruskal(G);
	return 0;
}
